using System;
using System.Collections;
using Slaks.VectorBasics;

namespace Slaks.Vectors.Algorithms
{
	public class KMeans
	{
		private VectorDistanceMeasure m_vectorDistanceMeasure;
		private int m_numberOfClusters;

		private VectorList[] m_vectorClusters;

		public KMeans(VectorList vectorList, int numberOfClusters, VectorDistanceMeasure vectorDistanceMeasure)
		{
			if (vectorList == null || vectorList.Count == 0) throw new VectorException("There are no vectors in the list");
			if (numberOfClusters <= 0) throw new VectorException("Number of clusters must be greater then 0");

			if (vectorList.Count < numberOfClusters) numberOfClusters = vectorList.Count;

			m_vectorDistanceMeasure = vectorDistanceMeasure;
			m_numberOfClusters = numberOfClusters;

			this.Init(vectorList, numberOfClusters);
		}

		public VectorList[] GetVectorClusters()
		{
			return m_vectorClusters;
		}

		private void Init(VectorList vectorList, int numberOfClusters)
		{
			m_vectorClusters = new VectorList[numberOfClusters];
			for (int i = 0; i < numberOfClusters; i++)
			{
				m_vectorClusters[i] = new VectorList();
			}

			int clusterNumber;
			Random rand = new Random(unchecked((int) DateTime.Now.Ticks));
			foreach (Vector vector in vectorList)
			{
				clusterNumber = rand.Next(numberOfClusters);
				m_vectorClusters[clusterNumber].Add(vector);
			}

			//assign first centroids
			for (int i = 0; i < numberOfClusters; i++)
			{
				Vector vector;
				if (m_vectorClusters[i].Count > 0)
				{
					vector = m_vectorClusters[i][0];
					m_vectorClusters[i].SetCentroid(vector);
				}
			}
		}

		/// <summary>
		/// Get the number of clusters
		/// </summary>
		/// <returns></returns>
		public int GetNumberOfClusters()
		{
			return m_numberOfClusters;
		}

		/// <summary>
		/// Apply the Shenker Algorithm
		/// </summary>
		public void Apply()
		{
			bool isChanged = true;

			while (isChanged == true)
			{
				isChanged = this.DetermineCentroids();
				if (isChanged == true)
				{
					this.AssignVectors();
					//this.CheckValidity();
				}
			}
		}

		/// <summary>
		/// Determine centroids for clusters and return whether the centroids were changed
		/// </summary>
		/// <returns>true if centroids were altered otherwise return false</returns>
		private bool DetermineCentroids()
		{
			bool isChanged = false;
			bool result;
			foreach (VectorList vectorCluster in m_vectorClusters)
			{
				result = vectorCluster.DetermineCentroid(m_vectorDistanceMeasure);
				if (result == true) isChanged = true;
			}
			return isChanged;
		}

		private void AssignVectors()
		{
			double minDistance;
			double tempDistance;
			int cluster = 0;
			Vector centroid;
			Vector currentVector;

			//holds vectors that must be removed
			ArrayList vectorsToRemove = new ArrayList();
			for (int i = 0; i < m_vectorClusters.Length; i++)
			{
				vectorsToRemove.Clear();

				for (int j = 0; j < m_vectorClusters[i].Count; j++)
				{
					minDistance = double.MaxValue;
					cluster = i; //current cluster to which currentvector belongs
					currentVector = m_vectorClusters[i][j];

					if (currentVector == m_vectorClusters[i].GetCentroid()) continue;

					for (int k = 0; k < m_vectorClusters.Length; k++)
					{
						centroid = m_vectorClusters[k].GetCentroid();
						if (centroid == null) continue;
						tempDistance = m_vectorDistanceMeasure(centroid, currentVector);
						if (minDistance > tempDistance)
						{
							minDistance = tempDistance;
							cluster = k;
						}
					}

					//the vector belongs to another cluster
					if (cluster != i)
					{
						m_vectorClusters[cluster].AddVectorToTemporalList(currentVector);
						vectorsToRemove.Add(currentVector);
					}
				} //end of for

				foreach (Vector vector in vectorsToRemove)
				{
					m_vectorClusters[i].Remove(vector);
				}


			} //end of for

			for (int i = 0; i < m_vectorClusters.Length; i++)
			{
				m_vectorClusters[i].MergeTemporalList();
			}

		}

		public int CountVectors()
		{
			int count = 0;
			foreach (VectorList cluster in this.GetVectorClusters())
			{
				count += cluster.Count;
			}
			return count;
		}

		#region Debug function to check validity of each vector that is assigned to the cluster

		/// <summary>
		/// Check each vector with each cluster and tell whether the newly assigned vector is in cluster 
		/// whose distance greater then distance to another cluster
		/// </summary>
		/// <returns></returns>
		public void CheckValidity()
		{
			double minDistance;
			double tempDistance;
			int cluster = 0;
			Vector centroid = null;
			Vector currentVector;

			for (int i = 0; i < m_vectorClusters.Length; i++)
			{
				for (int j = 0; j < m_vectorClusters[i].Count; j++)
				{
					minDistance = double.MaxValue;
					cluster = i; //current cluster to which currentvector belongs
					currentVector = m_vectorClusters[i][j];

					if (currentVector == m_vectorClusters[i].GetCentroid()) continue;

					for (int k = 0; k < m_vectorClusters.Length; k++)
					{
						centroid = m_vectorClusters[k].GetCentroid();
						if (centroid == null) continue;
						tempDistance = m_vectorDistanceMeasure(centroid, currentVector);
						if (minDistance > tempDistance)
						{
							minDistance = tempDistance;
							cluster = k;
						}
					}

					//the vector belongs to another cluster
					if (cluster != i)
					{
						Console.WriteLine(currentVector.Name + " is in cluster of centroid " +
							centroid.Name + " distance : " +
							m_vectorDistanceMeasure(centroid, currentVector) + "\nbut its distance less to cluster number " + cluster +
							" with centroid " + m_vectorClusters[cluster].GetCentroid().Name + " and distance " +
							m_vectorDistanceMeasure(currentVector, m_vectorClusters[cluster].GetCentroid()) + Environment.NewLine);
					}
				} //end of for
			} //end of for
		}

		#endregion
	}
}